/**
 * 面试题 02.08. 环路检测
 * https://leetcode-cn.com/problems/linked-list-cycle-lcci/
 */
public class Solutions_mianshi_02_08 {
    public static void main(String[] args) {
//        int[] arr = {3, 2, 0, -4};  // output: 2
//        ListNode head = MyLinkedListUtils.ArrayToListNode(arr, 1);

//        int[] arr = {1, 2};  // output: 1
//        ListNode head = MyLinkedListUtils.ArrayToListNode(arr, 0);

        int[] arr = {1};  // output: null
        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);

        ListNode result = detectCycle(head);
        System.out.println(result);
    }

    /**
     * 计算过程推理：
     *      1 --- 2 --- 3 --- 4 --- 5 --- 6
     *                  |                  |
     *                 12                 7
     *                 |                  |
     *                11 --- 10 --- 9 --- 8
     *
     * 有环形链表如上所示：
     * 入环结点为 3
     * 若快指针 fast，慢指针 slow 同时从结点 1 出发（fast 每次 2 步，slow 每次 1 步）
     * 最终将在结点 11 相遇，此时，慢指针走了 11 - 1 = 10 步，而快指针走了 21 - 1 = 20 步
     *     fast    slow
     *     1         1
     *     2         3
     *     3         5
     *     4         7
     *     5         9
     *     6         11
     *     7         3
     *     8         5
     *     9         7
     *     10        9
     *     11        11
     * 设定几个变量：
     * x：链表头结点到环的入口结点的距离（如上图所示，x 的长度为 3 - 1 = 2）
     * y：相遇时，从环的入口结点 3 到相遇结点 11 的距离（如上图所示，y 的长度为 11 - 3 = 8）
     * R：环的长度（如上图所示，环的长度为 12 - 3 + 1 = 10）
     * 慢指针走的步数设为 a，则 a = x + y（两段距离：头结点到环入口结点(x)，环入口结点到相遇结点(y)）
     * 快指针走的步数设为 b，则 b = 2a（快指针走的距离是慢指针走的距离的 2 倍），
     *      且 b = x + y + NR（快指针同样走了 x 和 y 的路程，NR 表示走了 N 圈环的长度，N 大于等于 1）
     * 将 a 代入 b 中，求解 x：
     * 化简公式：2(x + y) = x + y + NR
     *          2x + 2y = x + y + NR
     *               x = NR - y
     * 即 x 的长度就是 环的长度 减 y 的长度
     * 而此时的快慢指针正好处在相遇节点上，即从相遇结点再走 (NR - y) 个单位的距离，就可以到达环的入口结点
     * 那么将 slow 或者 fast 任一指针，重新指向链表头结点，两指针同时再走 x 个距离后，会再次相遇，且相遇结点一定为环的入口结点
     * 推论总结：相遇结点到环的入口结点，和链表头结点到环的入口结点，是长度相等的
     */
    public static ListNode detectCycle(ListNode head) {
        // 定义快慢双指针
        ListNode fast = head, slow = head;
        // 判断 head 中是否存在环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 最终快慢指针指向相同时，结束循环
                break;
            }
        }
        // 若无环，最终 fast 将指向 null
        // 若有环，最终 fast 和 slow 将指向同一结点
        if (fast == null || fast.next == null) {
            return null;
        }
        // 若有环，查找环的入口结点
        slow = head;
        // slow 重新指向链表头结点，与 fast（此时 fast 指向的是相遇结点）
        // 一起走（每次走一步），当两指针指向结点相同时，相遇结点即是环的入口结点
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
